#pragma once

////////////////////////
//二叉树类型定义

template <typename E>
struct BiTNode
{
    E data;
    BiTNode *lchild, *rchild;
};

template <typename E>
using BiTree = BiTNode<E> *;

/////////////////////////
//二叉树基本操作

///先序遍历二叉树  Preorder(T,visit)
template <typename E, typename F>
void Preorder(BiTree<E> T, F visit)
{
    if (T)
    {
        visit(T->data);
        Preorder(T->lchild, visit);
        Preorder(T->rchild, visit);
    }
}
///中序遍历二叉树 Inorder(T,visit)
template <typename E, typename F>
void Inorder(BiTree<E> T, F visit)
{
    if(T){
        Inorder(T->lchild,visit);
        visit(T->data);
        Inorder(T->rchild,visit);
    }
}

///后序遍历二叉树 postorder(T,visit)
template <typename E, typename F>
void Postorder(BiTree<E> T, F visit)
{
    if(T){
        Postorder(T->lchild,visit);
        Postorder(T->rchild,visit);
        visit(T->data);
    }
}

///求二叉树结点数
template <typename E>
int NodeCount(BiTree<E> T)
{
    if(T == nullptr)
    return 0;
    
    auto  L =NodeCount(T->lchild);
    auto  R =NodeCount(T->rchild);
    return L+R+1;
}

///求二叉树叶子结点数
template <typename E>
int LeafCount(BiTree<E> T)
{
if(T == nullptr)
    return 0;
    if(T ->lchild==nullptr&&T->rchild==nullptr)
    return 1;
    auto  L =LeafCount(T->lchild);
    auto  R =LeafCount(T->rchild);
    return L+R;
}
///求二叉树深度
template<typename E>
int Depth(BiTree<E> T)
{
    if(T==nullptr)
    return 0;
    auto L = Depth(T->lchild);
    auto R = Depth(T->rchild);
    return L>R ? L+1:R+1;
}
#include <iostream>
using std :: cout;
using std::endl;
///打印二叉树
template<typename E>
void Print(BiTree<E> T,char prefix ='$',int level =0)
{
    if(T){
        Print(T->rchild,'/',level+1);
        for(int i =0; i<level; ++i)cout<<"  ";
cout<<prefix << ' ' <<T->data<<endl;
Print(T->lchild,'\\',level+1);
    }
}
#include <iostream>
using std::cin;
using std::noskipws;

///建立二叉树
BiTree<char> CreateBinaryTree()
{
    char c;
    cin >> noskipws >> c;
    if(c == ' ')return nullptr;
    auto T =new BiTNode<char>{c,nullptr,nullptr};
    T->lchild=CreateBinaryTree();
    T->rchild=CreateBinaryTree();
    return T;
}

///销毁二叉树
template <typename E>
void Destroy(BiTree<E> &T)
{
    if(T){
        Destroy(T->lchild);
         Destroy(T->rchild);
         delete T;
         T=nullptr;
        
 
    }
}
/////////////////////////////
//二叉排序树基本操作

///二叉排序树查找算法  searchBST(T，e)
template <typename E>
BiTree<E> SearchBST(BiTree<E> T,E e)
{
    if(!T||T->data == e)
    return T;
    else if(e<T->data)
    return SearchBST(T->lchild,e);
    else
      return SearchBST(T->rchild,e);
}
///二叉排序树找最小 FindMinBST(T)
template<typename E>
BiTree<E> FindMinBST(BiTree<E> T)
{
    if(T)
    while(T->lchild)
    T=T->lchild;
    return T;
}
///二叉排序树找最大 FindMaxBST(T)
template<typename E>
BiTree<E> FindMaxBST(BiTree<E> T)
{
    if(T)
    while(T->rchild)
    T=T->rchild;
    return T;
}
///二叉排序树插入InsertBST(&T,e)
template <typename E>
void InsertBST(BiTree<E> &T,E e)
{
    if(T==nullptr)
    T=new BiTNode<E>{e,nullptr,nullptr};
    else if(e<T->data)
    InsertBST(T->lchild,e);
    else if (e>T->data)
    InsertBST(T->rchild,e);
    else
    ;
}
///二叉排序树删除 DeleteBST(&T,e)
template<typename E>
void DeleteBST(BiTree<E> &T,E e )
{
    if(T==nullptr)return;
    else if(e <T->data)
    DeleteBST(T->lchild,e);
    else if(e <T->data)
    DeleteBST(T->rchild,e);
    else{//T->data==e
    if(T->lchild&&T->rchild){//T有两个子树
    T->data=FindMaxBST(T->lchild)->data;
    DeleteBST(T->lchild,T->data);
    }else{//T之多有一个子树
    auto oldNode=T;
    T=T->lchild? T->lchild:T->rchild;
    delete oldNode;
    }

    }
}